/**
 * describe:
 *
 * @author chaP
 * @date 2019/03/28
 */
package CodingTest.AC20190328;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目描述
 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
 */
public class Print {
    class TreeNode{
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val){
            this.val = val;
        }
    }
    //方法一：非递归法
    ArrayList<ArrayList<Integer>> Print1(TreeNode pRoot){
        if(pRoot == null) new ArrayList<>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(pRoot);
       while(!q.isEmpty()){
            int m = q.size();
            ArrayList<Integer> temp = new ArrayList<>();
            for(int i = 0;i<m;i++){
                TreeNode tempNode = q.poll();
                if(tempNode.left!=null){
                    q.offer(tempNode.left);
                }
                if(tempNode.right!=null){
                    q.offer(tempNode.right);
                }
                temp.add(tempNode.val);
            }
            res.add(temp);
        }
        return res;
    }
    //方法二：递归法：
    ArrayList<ArrayList<Integer>> Print2(TreeNode pRoot){
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        depth(pRoot,1,list);
        return list;

    }
    private void depth(TreeNode root,int depth,ArrayList<ArrayList<Integer>> list){
        if(root == null) return;
        if(depth > list.size()) //关键判断
            list.add(new ArrayList<Integer>());
        list.get(depth-1).add(root.val);
        depth(root.left,depth+1,list);
        depth(root.right,depth+1,list);
    }
}
